/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 * 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。有效括号组合需满足：左括号必须以正确的顺序闭合。
 * @param n
 */
 const generateParenthesis = (n: number): string[] => {
  const ans: string[] = [];

  /**
   * 深度优先
   * @param level 当前的层数
   * @param left 左括号有多少可以用
   * @param right 有括号还有多少可以用
   */
  const dfs = (str: string, left: number, right: number) => {
    // 左右剩余的括号都为0时·
    if (left === 0 && right === 0) {
      // 放入答案中
      ans.push(str);
      return;
    }

    // 剩余的左括号大于0
    if (left > 0) {
      dfs(str + "(", left - 1, right);
    }

    // 剩余的右括号大于0 
    // 并且剩余的左括号不等于剩余的右括号时, 因为剩余括号相等的时候一定不能先选右括号
    if (right > 0 &&  left !== right) {
      dfs(str + ")", left, right - 1);
    }
  };

  dfs("", n, n);

  return ans;
};


const generateParenthesis2 = (n: number): string[] => {
  const ans: string[] = [];

  /**
   * 深度优先
   * @param level 当前的层数
   * @param left 左括号有多少可以用
   * @param right 有括号还有多少可以用
   */
  const dfs = (str: string, left: number, right: number) => {
    if (left === 0 && right === 0) {
      // 放入答案中
      ans.push(str);
      return;
    }

    // 剩余的左括号大于剩余的右括号的数量, 不满足
    // e.g: str: '())'  left: 1, right: 0
    if (left > right) return;

    // 左括号大于0
    if (left > 0) {
      dfs(str + "(", left - 1, right);
    }

    // 右括号大于0
    if (right > 0) {
      dfs(str + ")", left, right - 1);
    }
  };

  dfs("", n, n);

  return ans;
};

console.log(generateParenthesis(2))
